home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / pcr / pcr4_4.lha / DIST / gc / GCstrategy.c < prev    next >
C/C++ Source or Header  |  1991-10-23  |  9KB  |  304 lines
  1. # include "xr/GCPrivate.h"
  2. # define TICKS_TO_WAIT 2  /* Normal sleep time for daemon */
  3.  
  4. /*
  5.  * Daemon that invokes collections of partial collections are enabled.
  6.  * If partial collections are enabled, it is the sole initiator of collections.
  7.  * If partial collections are disabled, the mutator invokes the collector
  8.  * by calling GC_full_collection.
  9.  * GC_partial_gc_strategy runs at high priority.  It forks low
  10.  * priority processes to do the background marking.
  11.  */
  12.  
  13. #define I_HOLD_ML(ml) (((XR_ML)(ml))->ml_holder == XR_currThread)
  14.  
  15. struct XR_CVRep neededCV = { 0 };
  16.  
  17. bool GC_stop_world_collection_needed = FALSE;
  18.                     /* Full stop-the-world collection  */
  19.                     /* requested asap.           */
  20. bool GC_full_collection_needed = FALSE; /* Full collection has been    */
  21.                     /* requested.            */
  22.                     
  23. bool GC_Need_incremental_gcP()
  24. {
  25.     register int c_in_use;
  26.     register int adj_words_allocd;
  27.     
  28.     if (GC_mode & GC_INCREMENTAL) {
  29.     /* Test whether allocation warrants a collection */
  30.         /* We count GC_mem_free almost as though it had never     */
  31.         /* been allocated.  We don't quite want to do this,      */
  32.         /* since a nonleaking client still needs to have storage    */
  33.         /* coalesced occasionally.  This is a bit time-critical;    */
  34.         /* hence the hack to avoid multiplication and division.    */
  35.         adj_words_allocd = GC_words_allocd - GC_mem_freed
  36.                                + (GC_mem_freed >> 3);
  37.         c_in_use = GC_composite_at_full_gc;
  38.         if (c_in_use < MIN_COMPOSITE_IN_USE) {
  39.           c_in_use = MIN_COMPOSITE_IN_USE;
  40.         }   
  41.         if (GC_partial_gc_allocs) {
  42.           return (adj_words_allocd > GC_partial_gc_allocs);
  43.         } else {
  44.           return (adj_words_allocd * GC_free_mem_ratio > c_in_use);
  45.         }
  46.     } else {
  47.     /* not incremental, so we'll only collect on demand */
  48.     return(FALSE);
  49.     }
  50. }
  51.  
  52. /* Delay caller sufficiently to allow collector to catch up.  Caller is */
  53. /* assumed to have allocated nbytes, and may be penalized         */
  54. /* proportionately.                            */
  55. /* Caller should avoid holding important locks.                */
  56. /* Caller should not hold allocation lock.                */
  57. void GC_delay_alloc(nbytes)
  58. long nbytes;
  59. {
  60.     static int counter = 0;
  61.     register int wait_ticks;
  62. #   define ONE_TICK_PENALTY 32768  /* This many bytes per 1 tick penalty   */
  63. #   define SMALL_OBJ_INTERVAL 8       /* 1 in every SMALL_OBJ_INTERVAL small  */
  64.                    /* object allocations will be penalized */
  65.                    /* one tick.                   */
  66. #   define MAX_PENALTY 2        /* Maximum introduced delay.        */
  67.     
  68.     if (GC_Need_incremental_gcP() && !GC_dont_gc) {
  69.         if (nbytes > ONE_TICK_PENALTY) {
  70.             XR_MonitorEntry(&GC_allocate_ml);
  71.             XR_Notify(&neededCV);
  72.             wait_ticks = nbytes/ONE_TICK_PENALTY;
  73.             if (wait_ticks > MAX_PENALTY) {
  74.                 wait_ticks = MAX_PENALTY;
  75.             }
  76.             GC_wait_for_gc(wait_ticks);
  77.             XR_MonitorExit(&GC_allocate_ml);
  78.         } else {
  79.             /* delay every once in a while */
  80.             counter ++;
  81.             if (counter % SMALL_OBJ_INTERVAL == 0) {
  82.                 XR_MonitorEntry(&GC_allocate_ml);
  83.                 XR_Notify(&neededCV);
  84.                 GC_wait_for_gc(1);
  85.                 XR_MonitorExit(&GC_allocate_ml);
  86.             }
  87.         }
  88.     }
  89. }
  90.  
  91. void
  92. GC_wait_until_gc_needed()
  93. {
  94.   while(1) {
  95.     /* Wait a while to give mutator a chance */
  96.     XR_WaitCV(&neededCV, NIL);
  97.  
  98.     /* collections allowed at all? */
  99.     if (!GC_dont_gc) {
  100.       if (GC_demand_collection) {
  101.       GC_demand_collection = FALSE;
  102.       return;
  103.       } else {
  104.       if (GC_Need_incremental_gcP()) {
  105.           return;
  106.       }
  107.       }
  108.     }
  109.     /* wait for the next one. */
  110.   }
  111. }
  112.  
  113. bool
  114. GC_Need_full_gcP()
  115. {
  116.   register int adj_words_allocd;
  117.   
  118.   if (!(GC_mode & GC_INCREMENTAL)) return(TRUE);
  119.   if (GC_full_collection_needed) return(TRUE);
  120.   if (GC_full_gc_allocs != 0) {
  121.       /* See explanation in Need_incremental_gcP */
  122.       adj_words_allocd = GC_words_allocd - GC_mem_freed
  123.                          + GC_mem_freed >> 3;
  124.       return(adj_words_allocd > GC_full_gc_allocs);
  125.   } else {
  126.       return(GC_composite_in_use + GC_atomic_in_use
  127.              > GC_words_at_full_gc
  128.                + GC_composite_at_full_gc/GC_free_mem_ratio);
  129.   }
  130. }
  131.  
  132. # define TOO_MANY_FAULTS 1000  /* Threshold for switching to careful */
  133.                                /* marking.                 */
  134.  
  135. bool GC_should_do_second_mark(initial_words_allocd) 
  136. unsigned long initial_words_allocd;
  137. {
  138. #   define SECOND_MARK_THRESHOLD 10000
  139.     /* If more than this many words are allocated during first par.    */
  140.     /* marking pass, we run a second one.                */
  141.     return (GC_words_allocd - initial_words_allocd > SECOND_MARK_THRESHOLD);
  142. }
  143.  
  144. bool GC_should_mark_carefully()
  145. {
  146.   return (GC_max_markfaults > TOO_MANY_FAULTS);
  147. }
  148.  
  149. bool GC_should_pre_collect()
  150. {
  151.   /* should do better than this.  We can also look to see if the partial
  152.      collection seems likely to free up much storage and look to see
  153.      if the full collection is likely to finish before storage runs
  154.      out. */
  155.   return (GC_mode & GC_PARALLEL);
  156. }
  157.  
  158. /* Make sure that GC_mode agrees with what was requested */
  159. void GC_update_mode()
  160. {
  161.     XR_MonitorEntry( &GC_allocate_ml );
  162.     if (GC_requested_mode != GC_mode) {
  163.         if ((GC_mode & DIRTY_BITS_REQUIRED)
  164.             && !(GC_requested_mode & DIRTY_BITS_REQUIRED)) {
  165.             XR_EndVD();
  166.         }
  167.         if (!(GC_mode & DIRTY_BITS_REQUIRED)
  168.             && (GC_requested_mode & DIRTY_BITS_REQUIRED)) {
  169.             XR_StartVD();
  170.         }
  171.         GC_mode = GC_requested_mode;
  172.     }
  173.     XR_MonitorExit( &GC_allocate_ml );
  174. }
  175.  
  176. void GC_daemon()
  177. {
  178.   XR_SetPriority(XR_PRI_SYS_FOREGROUND);
  179.   GC_lock_to_fixed_vp();
  180.       /* We need to run on the same processor as marker threads.      */
  181.       /* Otherwise we can't do directed yields to them.        */
  182.   XR_InitializeCondition(&neededCV, TICKS_TO_WAIT);
  183. # ifdef DIRTY_BITS
  184.     XR_GCSetMode(GC_PARALLEL | GC_INCREMENTAL);
  185. # endif
  186.  
  187.   GC_wait_until_gc_needed();
  188.  
  189.   while(1) {
  190.     GC_update_mode();
  191.     GC_demand_collection = FALSE;
  192.     GC_full_collection(GC_stop_world_collection_needed);
  193.     GC_stop_world_collection_needed = FALSE;
  194.     GC_full_collection_needed = FALSE;
  195.  
  196.     GC_words_at_full_gc = GC_my_atomic_in_use + GC_my_composite_in_use;
  197.     GC_composite_at_full_gc = GC_my_composite_in_use;
  198.     GC_wait_until_gc_needed();
  199.  
  200.     while(!GC_Need_full_gcP()) {
  201.       GC_demand_collection = FALSE;
  202.       GC_partial_collection();
  203.       GC_wait_until_gc_needed();
  204.     }
  205.   }
  206.   /* We don't ever get here. */
  207. }
  208.  
  209.  
  210. # define MAXHEAPWASTE 2
  211.  
  212. /* Request a collection */
  213. void GC_demand_and_dont_wait()
  214. {
  215.     GC_demand_collection = TRUE;
  216.     GC_start_daemon();
  217.     XR_Notify(&neededCV);
  218. }
  219.  
  220. /* assumes that the allocate lock is held       */
  221. /* This starts a full stop-the-world collection */
  222. void GC_demand_full_and_wait()
  223. {
  224.     GC_stop_world_collection_needed = TRUE;
  225.     GC_full_collection_needed = TRUE;
  226.     GC_demand_and_dont_wait();
  227.     GC_wait_for_gc(XR_WAIT_FOREVER);
  228. }
  229.  
  230. bool GC_should_collect_on_heap_full()
  231. {
  232.     if (GC_dont_gc) return(FALSE);
  233.     if (GC_mode & (GC_INCREMENTAL|GC_PARALLEL)) {
  234.         return(MAXHEAPWASTE*(GC_composite_in_use + GC_atomic_in_use)
  235.                < BYTES_TO_WORDS(GC_heapsize) );
  236.     } else {
  237.         return(TRUE);
  238.     }
  239. }
  240.  
  241. /* Expand heap if there was a recent collection, otherwise collect */
  242. /* We hold GC_allocate_ml                       */
  243. static void GC_expand_or_collect(min_words)
  244. register long min_words;
  245. {
  246.     register long min_blocks =
  247.           divHBLKSZ(WORDS_TO_BYTES(min_words) + 2 * HBLKSIZE - 1);
  248.           
  249.     if (GC_words_allocd * GC_free_mem_ratio > GC_composite_in_use) {
  250.         GC_demand_full_and_wait();
  251.     } else {
  252.         int blocks_to_get = divHBLKSZ(
  253.                     WORDS_TO_BYTES(
  254.                         GC_composite_in_use
  255.                         - GC_words_allocd * GC_free_mem_ratio)
  256.                     + 2 * HBLKSIZE);
  257.         if ( blocks_to_get > MAX_HINCR ) blocks_to_get = MAX_HINCR;
  258.         if ( blocks_to_get < MIN_HINCR ) blocks_to_get = MIN_HINCR;
  259.         if ( min_blocks  > blocks_to_get ) blocks_to_get = min_blocks;
  260.         GC_expand_hp(blocks_to_get, FALSE);
  261.     }
  262. }
  263.  
  264. /* assumes that the allocate lock is held */
  265. void GC_heap_full()
  266. {
  267.   /* well, I don't like this much.
  268.      First try to free some blocks.  If THAT fails, demand a collection */
  269.   GC_reclaim_empty_pages();
  270.   if (!GC_sufficient_hb(1)) {
  271.     if (GC_should_collect_on_heap_full()) {
  272.       GC_expand_or_collect(1);
  273.     }
  274.   }
  275. }
  276.  
  277. /* assumes that the allocate lock is held */
  278. void GC_reclaim_hblks(lw)
  279. long lw;
  280. {
  281.   /* well, I don't like this much either.
  282.      First try to free some blocks.  If THAT fails, demand a collection */
  283.   GC_reclaim_empty_pages();
  284.   if (!GC_sufficient_hb(lw)) {
  285.     if (GC_should_collect_on_heap_full()) {
  286.  
  287.       GC_expand_or_collect(abs(lw));
  288.  
  289.       if (!(GC_sufficient_hb(lw))) {
  290.     GC_reclaim_empty_pages();
  291.     /* should we have something here demanding a full collection? */
  292.       }
  293.     }
  294.   }
  295. }
  296.  
  297. void XR_GCollect()
  298. {
  299.   XR_MonitorEntry(&GC_allocate_ml);
  300.   GC_demand_full_and_wait();
  301.   XR_MonitorExit(&GC_allocate_ml);
  302. }
  303.  
  304.